package com.jack.leetcode.eachproblem_2020;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 单词拆分2 {

    public static void main(String[] args) {
        List<String> words = Arrays.asList("aaaa","aa","a");
        wordBreak("aaaaaaa", words);
    }

    public static List<String> wordBreak(String s, List<String> wordDict) {
        int n = wordDict.size();
        boolean[] isVisited = new boolean[n];
        List<String> result = new ArrayList<>();
        recv(s, wordDict, 0, result, new ArrayList<>());
        result.forEach(r -> System.out.println(r));
        return result;
    }

    private static void recv(String s, List<String> wordDict,
                      int index, List<String> tmp, List<String> result){
        if(index == s.length()){
            tmp.add(String.join(" ", result));
            return;
        }
        for(int i = 0;i < wordDict.size();i++){
            String s1 = wordDict.get(i);
            boolean shouldExecute = index + s1.length() <= s.length() &&
                    s.substring(index, index + s1.length()).equalsIgnoreCase(s1);
            if(shouldExecute){
                result.add(s1);
                recv(s, wordDict, index + s1.length(), tmp, result);
                result.remove(s1);
            }
        }
    }
}
